package com.leetcode.algorithm.y22.m09.w1;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 406. 根据身高重建队列
 * 
 * https://leetcode.cn/problems/queue-reconstruction-by-height/
 * 
 * @author jie.deng
 *
 */
class Question0406Solution01 {

	public int[][] reconstructQueue(int[][] people) {
		// 需要考虑两个维度的情况
		// 先从大到小按照h排个序，再来贪心k
		// 局部最优：优先按身高高的people的k来插入。插入操作过后的people满足队列属性
		// 全局最优：最后都做完插入操作，整个队列满足题目队列属性
		int len = people.length;
		Arrays.sort(people, (arr1, arr2) -> arr2[0] == arr1[0] ? arr1[1] - arr2[1] : arr2[0] - arr1[0]);
		List<int[]> list = new LinkedList<>();
		for (int i = 0; i < len; i++) {
			list.add(people[i][1], people[i]);
		}

		for (int i = 0; i < len; i++) {
			people[i] = list.get(i);
		}
		return people;
	}

}